home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / basic / ubmalm.zip / spspt.ub < prev    next >
Text File  |  1990-08-22  |  599b  |  17 lines

  1.    10   fnSpspt(N,B)
  2.    15   ' Strong pseudoprime test of N using witness B.  21 May 1990.
  3.    20   local Q,M,I,Count=0,F%=0
  4.    30   if N<2 then return(0) endif
  5.    40   M=N-1
  6.    50   repeat Q=M\2:if not res then M=Q:inc Count endif
  7.    70   until res
  8.    80   ' Now n-1 = (2^count)*m with m odd.
  9.    90   Q=modpow(B,M,N):if Q=0 then return(0) endif
  10.   110   if or{Q=1,Q=N-1} then F%=1 else I=1
  11.   120   :while and{I<Count,F%=0}
  12.   130   :Q=(Q*Q)@N
  13.   140   :if Q=N-1 then F%=1 else if Q=1 then I=Count endif endif
  14.   150   :inc I
  15.   160   :wend endif
  16.   170   return(F%) 'End of function Spspt
  17.